package main.leetcode.offer.firstround.from03to50;

import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * 49.丑数
 *
 * <p>我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 *
 * <p>
 *
 * <p>示例:输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 *
 * <p>说明:1 是丑数。 n 不超过1690。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/chou-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex49 {
    public static void main(String[] args) {
        System.out.println(new ex49().nthUglyNumber(1690));
    }

    public int nthUglyNumber(int n) {
        Ugly ugly = new Ugly();
        return ugly.uglyNumbers[n - 1];
    }
}

class Ugly {
    int[] uglyNumbers = new int[1690];

    // 小顶堆/优先队列
    Ugly() {
        // 为什么这里要用long而不能用int
        // 在进行*步骤时会发生溢出现象，而小顶堆也就是优先队列会直接把溢出的丑数放到队首，因此之后得到的数全都会是复数
        // 小顶堆中存放过的丑数超过1690，必有超出int上限的数
        HashSet<Long> set = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        set.add(1L);
        queue.add(1L);
        int[] primes = new int[] {2, 3, 5};
        long currUgly, newUgly;
        for (int i = 0; i < 1690; i++) {
            currUgly = queue.poll();
            uglyNumbers[i] = (int) currUgly;
            for (int p : primes) {
                newUgly = p * currUgly; // *在这里会产生溢出
                if (set.add(newUgly)) {
                    queue.add(newUgly); // 在这一步，生成的复数会直接放到队首
                }
            }
        }
    }

    // 动态规划/三指针
    //    Ugly() {
    //        int i2 = 0, i3 = 0, i5 = 0;
    //        int ugly;
    //        uglyNumbers[0] = 1;
    //        for (int i = 1; i < 1690; i++) {
    //            ugly =
    //                    Math.min(
    //                            Math.min(uglyNumbers[i2] * 2, uglyNumbers[i3] * 3),
    //                            uglyNumbers[i5] * 5);
    //            uglyNumbers[i] = ugly;
    //            if (ugly == uglyNumbers[i2] * 2) ++i2;
    //            if (ugly == uglyNumbers[i3] * 3) ++i3;
    //            if (ugly == uglyNumbers[i5] * 5) ++i5;
    //        }
    //    }
}
